package com.wx.leetcode;

import com.wx.ArrayUtils;

/**
 * @desc: 计算数组每个数最小左子的和
 * <p>
 * 举个栗子
 * 4, 1, 3, 5, 0, 6
 * 1左边没有比它小的，不计数
 * 3左边1比它小，计数1
 * 5左边，4，1，3都比它小，计数8
 * 0左边没有比它小的，不计数
 * 6左边，5，3，，1，4都比它小，计数13
 * 最后算总和，1+8+13 = 22
 * @author: wx
 * @time: 2020/3/30 1:11 PM
 */
public class LeftMInSum {


    public static int run(int[] array) {

        if (ArrayUtils.arrayValidation(array)) {
            return 0;
        }

        return mergeRun(array, 0, array.length - 1);
    }

    /**
     * 二分求和
     */
    private static int mergeRun(int[] array, int startIndex, int endIndex) {

        if (startIndex == endIndex) {
            return 0;
        }

        int middle = startIndex + (endIndex - startIndex) / 2;

        return mergeRun(array, startIndex, middle)
                + mergeRun(array, middle + 1, endIndex)
                + excretion(array, startIndex, middle, endIndex);

    }

    /**
     * 外排计算最小值和
     */
    private static int excretion(int[] array, int startIndex, int middle, int endIndex) {

        int[] temp = new int[endIndex - startIndex + 1];
        int i = 0;
        int startIndexAdd = startIndex;
        int middleAdd = middle + 1;
        int count = 0;

        while (startIndexAdd <= middle && middleAdd <= endIndex) {
            if (array[startIndexAdd] < array[middleAdd]) {
                count += array[startIndexAdd];
                temp[i++] = array[startIndexAdd];
                startIndexAdd++;
            } else {
                temp[i++] = array[middleAdd++];
            }
        }

        if (startIndexAdd <= middle) {
            count += (middle - startIndexAdd) * count;
            while (startIndexAdd <= middle) {
                temp[i++] = array[startIndexAdd++];
            }
        }

        if (middleAdd <= endIndex) {
            count += (endIndex - middleAdd) * count;
            while (middleAdd <= endIndex) {
                temp[i++] = array[middleAdd++];
            }
        }

        for (int j = 0; j < temp.length; j++) {
            array[startIndex++] = temp[j];
        }

        return count;
    }

    public static void main(String args[]) {
        int[] minArray = {4, 1, 3, 5, 0, 6};
        System.out.println("最小值:" + run(minArray));
    }

}
